Problema computazionale

Nell'informatica teorica, un problema computazionale o problema astratto è una relazione tra un insieme di istanze e un insieme di soluzioni. Un problema computazionale permette di stabilire formalmente la relazione desiderata tra l'entrata o input di un algoritmo e la sua uscita o output. Una soluzione algoritmica a un problema computazionale consiste in un algoritmo che per ogni istanza del problema calcola almeno una soluzione corrispondente – nel caso esista – o certifica che non esiste alcuna soluzione. Un problema astratto diventa un problema concreto quando le istanze e le soluzioni sono codificate in forma di linguaggi formali.

I problemi computazionali sono soliti essere definiti in due parti: nella prima si descrive l'insieme di istanze e nella seconda si descrive la soluzione attesa per ogni istanza. Per esempio, il problema dell'ordinamento di numeri interi si definisce di solito come segue:

Istanza: Una successione finita di numeri interi ${\displaystyle \left(a_{1},a_{2},\ldots ,a_{n}\right)}$

Soluzione: Una permutazione ${\displaystyle \left(a_{1}^{\prime },a_{2}^{\prime },\ldots ,a_{n}^{\prime }\right)}$ della successione in entrata tale che ${\displaystyle a_{1}^{\prime }\leq a_{2}^{\prime }\leq \cdots \leq a_{n}^{\prime }}$

Qui tanto l'insieme delle istanze quanto quello delle soluzioni è lo stesso, poiché si tratta dell'insieme di tutte le successioni finite di numeri interi. La relazione che vi è tra di essi assegna a ogni successione ${\displaystyle \left(a_{1},a_{2},\ldots ,a_{n}\right)}$ l'unica permutazione ${\displaystyle \left(a_{1}^{\prime },a_{2}^{\prime },\ldots ,a_{n}^{\prime }\right)}$ tale che ${\displaystyle a_{1}^{\prime }\leq a_{2}^{\prime }\leq \cdots \leq a_{n}^{\prime }}$. Ad esempio, ${\displaystyle \left(6,9,4,5\right)}$ ha come soluzione ${\displaystyle \left(4,5,6,9\right)}$. Una soluzione algoritmica al problema dell'ordinamento è quella dell'ordinamento a bolle, perché questo algoritmo produce una soluzione come uscita ogni volta che gli si somministra una istanza come entrata.